​论文笔记：稀疏移动人群感应的差异化位置隐私性

摘要：分散式移动人群感应（MCS）已经成为一种引人注目的方法，可以获取并推断城市规模的传感数据。然而，当参与者以其实际传感位置报告数据时，他们的位置隐私会受到威胁。为了解决这个问题，我们在稀疏MCS中采用了 "差分隐私"（differential-privacy）来为参与者的位置隐私提供理论上的保证，而不考虑对手的先验知识。此外，为了减少差分位置混淆造成的数据质量损失，我们提出了一个包含三个部分的隐私保护框架。首先，我们学习一个数据调整函数，将原始传感数据拟合到混淆后的位置。其次，我们应用一个线性程序来选择一个最佳的位置混淆函数，其目的是使数据调整的不确定性最小化。我们还提出了一种快速近似的变体。第三，我们提出了一种不确定性感知推理算法，以提高混淆数据的推理精度。用真实环境和流量数据集进行的评估表明，与现有的差分隐私方法相比，我们的最优方法可降低高达42%的数据质量损失。

1

介绍

移动人群感知（MCS）是一种新兴的范例，它利用最近配备传感器的智能手机的激增来收集城市规模的信息，例如噪音和交通。但是，目标检测区域有时可能会很大，以致于由于预算或时间限制而难以获得足够的移动用户空间覆盖范围。一种解决方案是使用稀疏移动人群感应，通过结合历史记录和来自附近区域的可用感应数据来估算未发现区域的信息。在稀疏MCS中，参与者报告带有时间戳和地理坐标的传感数据，这可能会带来严重的隐私风险。因此，确保位置隐私对于吸引参与者至关重要。

基于位置的系统（LBS）上的大量工作都研究了位置隐私，并提出了两种通用的保护机制[5]：（i）通过匿名保护用户的身份，以使他们的位置踪迹无法链接到特定的个人， （ii）使用位置混淆功能来更改暴露给服务提供商的用户的实际位置。本文关注混淆。

隐蔽(cloaking )是最流行的混淆机制之一。它将用户的位置表示为包含多个细粒度单元格而不是特定位置或单元格的隐蔽区域。但是，如果对手事先了解目标用户的位置分布，伪装的有效性就会大大降低。例如，如果用户出现的隐身区域由学校和政府机关组成，并且已知该用户是学生，则对手可以相当有把握地得出该用户将在学校的结论。

为了解决这个问题，人们引入了差分隐私，以确保用户从任何一个实际位置被映射到一个特定的混淆位置的概率是相似的。每个区域的概率越相似，就越难推断用户的原始位置，从而达到更好的隐私保护。

在传统的LBS中，应用差分隐私引入的数据损失是由实际位置和混淆位置之间的距离来衡量的。然而，在稀疏MCS中，数据质量损失是由实际位置和混淆位置之间的传感数据差异决定的，而不是地理距离。换句话说，只要两个位置的传感值足够接近，参与者的位置就可能被映射到远处的地方。因此，我们不需要直接使用现有的LBS算法，而是需要重新设计Sparse MCS应用的混淆机制。

在本文中，我们探讨了如何在空间MCS应用程序的位置隐私保护机制中平衡三个关键要素：参与者的隐私要求，对手对参与者实际位置分布的先验知识以及位置混淆带来的数据质量下降。这项工作的主要贡献是：

1）据我们所知，这是在减少数据质量损失的同时将差分隐私应用于稀疏MCS的第一项工作。

2）保证质量的隐私保护框架，包括三个部分：（i）数据调整功能，将原始感测数据拟合到混淆位置；(ii)最优混淆函数DUM-εe及其快速近似值FDUM-εe，在ε-差分隐私和均匀分布混淆的约束下，使数据调整的不确定性最小化；(iii)不确定性感知推理算法，提高混淆数据的推理精度。

3）对真实温度和流量监控数据集的实证评估，验证了与现有的差异隐私机制相比，我们的DUM-εe框架可以将数据质量损失降低多达42％；与DUM-εe相比，FDUM-εe将质量损失增加<3％，但仅占计算时间的<1％。

2


稀疏的MCS

稀疏的MCS用例。假设组织者在目标城市区域（划分为细粒度区域）中启动温度监视任务。目标是根据选定参与者的感应结果，每小时（感应周期）更新一次温度图。这些参与者需要将智能手机上感测到的温度以及实际感测位置上传到服务器（请参见图1（2-Top））。通常，在预算有限的情况下，选定的参与者无法完全覆盖该区域。因此，服务器需要推断出被忽略区域的温度值（请参见图1（3-Top））。

•收集传感矩阵。数据推理的模型是一个矩阵完成的问题：让收集传感矩阵（C）作为记录从参与者收集数据的矩阵，使得C [r，t]代表周期t中区域r的数据。如果在周期t中没有参与者从区域r上传数据，则C [r，t]是未知的。稀疏MCS任务成功的关键是确定一种高质量，低不确定性的推理算法来填充丢失的数据。

•数据推断算法。最近，压缩感知被证明在推断城市传感数据如温度、交通等方面比其他大多数方法更准确，所以我们将其作为本文的推理方法。

•根据压缩感知理论的推论，Candes等人提出了将压缩感知应用于矩阵补全问题的两个关键假设:

1)数据分布均匀。为了保证有效的数据推断，需要观测数据的均匀分布。在稀疏MCS中，这意味着目标感知区域的感知区域应该是均匀分布的。

2）小数据不确定性。当采样条目中没有噪声或不确定性时，只要先前的假设成立，就可以准确地推断出矩阵中的缺失值。当采样条目包含噪声或不确定性时，总推理误差与采样条目的不确定性级别成比例。
在讨论质量优化的位置隐私保护机制的设计时，我们将重新审视两个基本假设。

3


位置隐私保护框架

稀疏MCS中的定期数据收集需要参与者报告其实际区域。使用混淆添加位置隐私保护可以减轻参与者的担忧，但是如果分配给混淆区域的传感数据不能代表实际情况，则可能导致数据质量损失。因此，我们设计了一个位置隐私保护框架，该框架包含两个独特的组件：位置混淆和数据调整。

图1 说明了针对温度监控用例的稀疏MCS的隐私保护过程，其中参与者将其混淆的位置报告给服务器，而不是其实际位置。图2是我们为稀疏MCS建议的位置隐私保护框架的概述。它由两层组成-服务器端和移动客户端。在稀疏MCS任务开始之前，服务器端基于历史感测数据，以离线方式生成概率混淆矩阵（步骤S1）和数据调整函数（步骤S2）。该矩阵将任何一个区域对另一个区域进行混淆的概率进行编码。我们可以通过仔细选择概率来保护用户的位置隐私，即使对手知道混淆矩阵，也可能无法从混淆后的对应区域准确推断出实际区域。数据调整功能用于降低由于区域混淆造成的数据不确定性。通过分析历史日志中任意两个区域的感测数据之间的相关性来学习。

在将混淆矩阵和数据调整功能预下载到他们的手机之后，参与者可以按如下方式在移动客户端上执行感测任务。首先，每部手机都会感知其实际位置。然后，基于概率混淆矩阵，它将关联区域映射到另一个区域（步骤M1）。之后，数据调整功能改变原始感测数据以适合模糊区域的性质（步骤M2）。然后，移动客户端将修改后的区域和数据上传到服务器。然后，服务器从所有混淆区域共同推断出完整的感测图，与实际数据相比，该图包含一定程度的不确定性（步骤S3）。接下来，我们介绍如何将差异位置隐私应用于稀疏MCS。

4


位置差分隐私

敌手模型：在本文中，我们主要讨论一种常见的对手模型--贝叶斯攻击。具体来说，假设对手对用户实际区域 r 的概率分布有一定的先验知识，表示为π(r)；同时，假设对手知道任何源区域r 和目标区域r∗ 的位置混淆概率P[r，r∗]，那么，如果对手观察到用户的混淆区域r∗ ，他可以根据贝叶斯规则预测用户位置的后验分布，表示为 σ(r)。

备注1：位置混淆处理是在智能手机端完成的，因此MCS服务器不知道参与者的真实位置（如对手）。

备注2：此攻击者模型是快照本地化攻击：攻击者只能使用当前报告的（混淆的）位置来推断参与者的实际区域。弹道攻击的研究将是我们未来的工作。

定义：在这种敌手模型下，我们在稀疏MCS中定义差分隐私的意图是约束敌手的后知比先知的改进，即σ（r）/π（r）。直观地讲，如果两个区域 r 和 r′ 有相似的概率被映射到 r∗，那么对手如果观察到 r∗，将无法区分真正的区域是 r 还是 r′ 。

定义1.  ε-differential-privacy：假设目标传感区域由一组区域R组成，那么概率混淆矩阵P 满足ε-差分隐私。

其中ε是表示隐私级别的参数，P [r, r∗]表示P中使 r 与 r∗ 混淆的条目。ε越小，隐私保护越强。注意，ε-differential-privacy只是对混淆矩阵的约束；因此，在给定一定ε的情况下，多个矩阵可以满足ε-differential-privacy。

隐私保证：我们可以证明ε-differential-privacy理论上限制了先前对抗模型（即σ（r）/π（r））中的知识获取，无论该对抗者的先前知识π（r）是什么。

定理1.如果混淆矩阵满足ε-差分隐私，那么对于具有任何先验知识 π 的对手，其后验知识 σ 满足：

5


减少数据质量损失的差分位置隐私

如上所述，可能存在许多满足 ε-差分隐私的混淆矩阵。我们的目标是选择一种可以最大程度减少由于位置混淆带来的数据质量损失的方法。

A.混淆的数据质量要求

回想一下，在常规的稀疏MCS任务中，为了推断出完整的感知矩阵，压缩感知理论假设（1）参与者从均匀分布的区域中报告，以及（2）他们所报告的感知数据是准确的。但是，引入差分位置隐私可能会满足以下两个要求：

1）均匀的区域分布。尽管所选参与者的实际位置分布是均匀的，但混淆区域的分布可能不平衡。考虑混淆矩阵的极端情况，其中无法将任何区域混淆到区域 i。然后，在收集的感测矩阵中，第i行的所有值都是未知的。

2）混淆区域的小数据不确定性。参与者的实际传感数据与原始区域相对应。虽然数据调整可以减少上报数据与混淆区域真实数据之间的差异，但经过这一过程，不可避免地仍存在一定的不确定性。

B.最优模糊矩阵生成

我们试图减少数据的不确定性，并控制位置混淆中产生的混淆区域的分布均匀性。为了实现第一个目标，我们优化选择了一个矩阵，该矩阵可以使混淆区域中报告的数据和真实数据之间的数据不确定性期望值最小。关于第二方面，我们向混淆矩阵引入了均匀性约束。

目标：数据不确定性最小化

减少数据不确定性的第一步是使用数据调整函数，以使原始传感数据适应混淆区域。由于环境数据通常具有较高的空间相关性，因此，我们基于原始区域和混淆区域的历史感测数据，学习了用于数据调整的线性回归模型。在我们的框架（图2）中，模型学习是在服务器上进行的（步骤S2），而线性拟合估计是在移动客户端上进行的（步骤M2）。

我们定义一个不确定性矩阵 U 来表示所提出的数据调整模型的内在误差或不确定性。请注意，可以通过线性回归调整模型的残差标准误差来计算 U [r，r *] ，即将区域 r 混淆为 r * 所引起的数据不确定性。

直觉上，不确定性越小，质量越好。因此，我们可以将问题表述为：寻找一个能够使U中数据不确定性的总体期望值最小的混淆矩阵P，即：

其中 p(r) 是任何一个参与者出现在区域 r (Σp（r）= 1）中的总体概率。通常将p（r）假定为均匀分布或建模为整体人类移动性模式（例如，通过匿名移动电话呼叫记录）。对于设计良好的稀疏MCS任务，p（r）应该大致均匀分布以确保数据质量。为简单起见，将p（r）设置为1 / | R |。（均匀）。然后，为了提高稀疏MCS的数据质量，目标是最小U，有以下约束：

约束1：ε-differential-privacy。P必须满足ε-differential-privacy（公式2）。

约束2：混淆区域分布均匀。被混淆的区域需要均匀分布，以保证推断的数据质量，即

线性规划:DUM -εe

以减少数据质量损失为目标，我们制定了一个线性程序，即 ε-差分隐私和均匀分布混淆（DUM-e）约束下的数据不确定性最小化，以获得最优的P :

等式 7是ε-differential-privacy；等式 8是均匀性约束；等式 9和等式 10是概率约束。

C.最佳混淆矩阵的快速逼近

DUM-εe需要在不同区域之间进行O(R3)比较，以确保ε-differential-privacy，这使其难以扩展。因此，我们对DUM-e进行近似, 以减少比较次数，同时仍确保ε-differential-privacy。

6


相关工作

近年来，由于基于位置的应用程序的日益普及，对位置隐私进行了广泛的研究。流行的地方隐私保护机制包括伪装和虚拟点。但是，他们都对对手对目标用户位置分布的先验知识很敏感。当在MCS中应用基于隐身的位置隐私保护时，存在相同的缺点，例如，这在该领域仍是一种普遍做法[24]。

最近，研究人员将差分隐私[8]引入基于位置的服务(LBS)[7]、[10]、[25]，以减轻对手的先验知识的影响。传统上，差分位置隐私通过应用适当选择的Laplacian噪声[7]，[25]，将用户的实际位置改变为一个模糊的位置。我们的工作建立在这一思想的基础上，同时考虑了混淆所产生的数据不确定性。我们提出通过线性编程来实现最佳的混淆，它可以优于拉普拉斯噪声。需要注意的是，[10]也使用线性编程来获得最优混淆函数，但他们试图通过最小化实际位置和混淆位置之间的预期距离来优化LBS服务，这不能直接适用于MCS。

To等人在MCS任务[26]的参与者招募过程中开发了差分隐私。由于他们的目标是在较短的旅行距离内实现较高的任务分配率，因此通过扰动特定区域内的总参与者数量来保持不同位置的隐私性，而不是像本文讨论的那样模糊任何特定用户的实际位置。

7



结论

本文提出了稀疏MCS的差分位置隐私框架。它考虑了所需的隐私保护级别，有关参与者位置分布的先验知识以及由于位置混淆而导致的数据质量损失。提出的框架包括：（1）数据调整函数；（2）线性程序及其快速逼近，以获得满足ε-differential-privacy的最优位置模糊矩阵；（3）不确定性感知数据推理算法 。对真实数据集的经验评估表明，我们的框架可以提供充分的隐私保护，并减少数据质量损失。将来，我们将通过添加其他隐私保护保证并放宽对用于学习混淆矩阵的准确数据的要求来扩展此框架。

参考文献

[1] D. Zhang, L. Wang, H. Xiong, and B. Guo, “4w1h in mobile crowd sensing,” IEEE Commun. Mag., vol. 52, no. 8, pp. 42– 48, 2014.

[2] R. K. Rana, C. T. Chou, S. S. Kanhere, N. Bulusu, and W. Hu, “Ear-phone: an end-to-end participatory urban noise mapping system,” in IPSN, 2010, pp. 105–116.

[3] Y. Zhu, Z. Li, H. Zhu, M. Li, and Q. Zhang, “A compressive sensing approach to urban traffic estimation with probe vehicles,” IEEE TMC, vol. 12, no. 11, pp. 2289–2302, 2013.

[4] L. Wang, D. Zhang, Y. Wang, C. Chen, X. Han, and A. M’hamed, “Sparse mobile crowdsencrowd sensingcrowd sensingsing: challenges and opportunities,” IEEE Commun. Mag., 2016  

[5] J. Krumm, “A survey of computational location privacy,” PUC, vol. 13, no. 6, pp. 391–399, 2009.

[6] M. Duckham and L. Kulik, “A formal model of obfuscation and negotiation for location privacy,” in Pervasive Computing. Springer, 2005, pp. 152–170.

[7] M. E. Andres, N. E. Bordenabe, K. Chatzikokolakis, and ´ C. Palamidessi, “Geo-indistinguishability: Differential privacy for location-based systems,” in CCS, 2013, pp. 901–914.

[8] C. Dwork, “Differential privacy,” in ICALP, 2006, pp. 1–12.

[9] F. McSherry and K. Talwar, “Mechanism design via differential privacy,” in FOCS, 2007, pp. 94–103.

[10] N. E. Bordenabe, K. Chatzikokolakis, and C. Palamidessi, “Optimal geo-indistinguishable mechanisms for location privacy,” in CCS, 2014, pp. 251–262.

[11] L. Kong, M. Xia, X. Liu, G. Chen, Y. Gu, and M. Wu, “Data loss and reconstruction in wireless sensor networks,” IEEE TPDS, vol. 25, no. 11, pp. 2818–2828, 2014.

[12] L. Wang, D. Zhang, A. Pathak, C. Chen, H. Xiong, D. Yang, and Y. Wang, “CCS-TA: quality-guaranteed online task allocondensingcation in compressive crowdsensing,” in UbiComp, 2015, pp. 683–694.

[13] E. J. Candes and Y. Plan, “Matrix completion with noise,” Proceedings of the IEEE, vol. 98, no. 6, pp. 925–936, 2010.

[14] H. Xiong, D. Zhang, L. Wang, and H. Chaouchi, “Emc3: Energy-efficient data transfer in mobile crowdsensing under full coverage constraint,” IEEE TMC, vol. 14, no. 7, pp. 1355– 1368, 2015.

[15] L. Caccetta and R. Haggkvist, “On diameter critical graphs,” ¨ Discrete Mathematics, vol. 28, no. 3, pp. 223–229, 1979.

[16] P. Erdos, A. R ˝ enyi, and V. S ´ os, “On a problem of graph ´ theory,” Studia Sci. Math. Hungar, vol. 1, pp. 215–235, 1966.

[17] Y. Koren, R. Bell, and C. Volinsky, “Matrix factorization techniques for recommender systems,” Computer, no. 8, pp. 30–37, 2009.

[18] S. Agrawal and J. R. Haritsa, “A framework for high-accuracy privacy-preserving mining,” in ICDE, 2005, pp. 193–204.

[19] F. Ingelrest, G. Barrenetxea, G. Schaefer, M. Vetterli, O. Couach, and M. Parlange, “Sensorscope: Application specific sensor network for environmental monitoring,” ToSN, vol. 6, no. 2, pp. 17:1–17:32, 2010.

[20] S. Kosta, A. Mei, and J. Stefa, “Large-scale synthetic social mobile networks with swim,” IEEE TMC, vol. 13, no. 1, pp. 116–129, 2014.

[21] J. Shang, Y. Zheng, W. Tong, E. Chang, and Y. Yu, “Inferring gas consumption and pollution emission of vehicles through a city,” in KDD, 2014, pp. 1027–1036.

[22] H. Kido, Y. Yanagisawa, and T. Satoh, “Protection of location privacy using dummies for location-based services,” in ICDE Workshops, 2005, pp. 1248–1248.

[23] A. Kapadia, N. Triandopoulos, C. Cornelius, D. Peebles, and D. Kotz, “Anonysense: Opportunistic and privacy-preserving context collection,” in Pervasive Computing. Springer, 2008, pp. 280–297.

[24] L. Pournajaf, D. A. Garcia-Ulloa, L. Xiong, and V. Sunderam, “Participant privacy in mobile crowd sensing task management: A survey of methods and challenges,” ACM SIGMOD Record, vol. 44, no. 4, pp. 23–34, 2016.

[25] R. Dewri, “Local differential perturbations: Location privacy under approximate knowledge attackers,” IEEE TMC, vol. 12, no. 12, pp. 2360–2372, 2013.

[26] H. To, G. Ghinita, and C. Shahabi, “A framework for protecting protecting protecting worker location privacy in spatial sourcingcing,” Proceedings of the VLDB Endowment, vol. 7, no. 10, pp. 919–930, 2014  

END

本文来源于博客园扑棱扑棱。原文链接：https://www.cnblogs.com/lxwen/p/14139562.html

往期推荐

欢迎投稿

邮箱：[e-mail]

参与更多讨论，请添加小编微信加入交流群